#!/usr/bin/env python

class SegmentTree:
    def __init__(self, nums = None):
        if nums is None:
            self._tree = None
            self._size = 0
        else:
            self._tree = self.build_segment_tree(nums)
            self._size = len(nums)

    def build_segment_tree(self, nums):
        n = len(nums)
        tree = [0] * 2 * n

        for i in range(n, 2 * n):
            tree[i] = nums[i - n ]

        for i in range(n - 1, 0, -1):
            tree[i] = tree[2 * i + 1] + tree[2 * i]

        return tree

    def update(self, idx, val):
        # self._tree[idx + self._size] = val
        # parent = (self._size + idx) // 2
        # while parent > 0:
        #     self._tree[parent] = self._tree[2 * parent] + self._tree[2 * parent + 1]
        #     parent //= 2
        index = self._size + idx
        diff = val - self._tree[index]
        while index > 0:
            self._tree[index] += diff
            index //= 2

    def query(self, start, end):
        res = 0
        start += self._size
        end += self._size
        while start <= end:
            if start % 2 == 1:
                res += self._tree[start]
                start += 1

            if end % 2 == 0:
                res += self._tree[end]
                end -= 1

            start //= 2
            end //= 2
        return res

    def __str__(self):
        return str(self._tree)

def build_tree(arr, tree, node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        left = 2 * node + 1
        right = 2 * node + 2
        mid = start + (end - start) // 2

        build_tree(arr, tree, left, start, mid)
        build_tree(arr, tree, right, mid + 1, end)
        tree[node] = tree[left] + tree[right]

def update_tree(arr, tree, node, start, end, index, val):
    if start == end:
        arr[index] = val
        tree[node] = arr[start]
        return 

    mid = start + (end - start) // 2
    left = 2 * node + 1
    right = 2 * node + 2
    if index >= start and index <= mid:
        update_tree(arr, tree, left, start, mid, index, val)
    else:
        update_tree(arr, tree, right, mid + 1, end, index, val)
    
    tree[node] = tree[left] + tree[right]

def query_tree(arr, tree, node, start, end, L, R):
    if R < start or L > end:
        return 0
    elif start == end:
        return tree[node]
    elif L <= start and R >= end:
        return tree[node]
    else:
        mid =  start + (end - start) // 2
        left = 2 * node + 1
        right = 2 * node + 2
        sum_left = query_tree(arr, tree, left, start, mid, L, R)
        sum_right = query_tree(arr, tree, right, mid + 1, end, L, R)

        return sum_left + sum_right


if __name__ == '__main__':
    tree = SegmentTree([4, 6, 3, 7])
    print(tree)
    tree.update(2, 7)
    print(tree)
    tree.update(3, 3)
    print(tree)
    print(tree.query(1, 3))

    nums = [1, 3, 5, 7, 6, 11]
    tree = [0] * 4 * len(nums)
    build_tree(nums, tree, 0, 0, len(nums) - 1)
    print(tree)
    print(query_tree(nums, tree, 0, 0, len(nums) - 1, 2, 5))
    update_tree(nums, tree, 0, 0, len(nums) - 1, 4, 9)
    print(tree)
    print(nums)
    


